1. Field of the Invention
The present invention relates to inverse halftoning of digital images, and particularly to a system and method of inverse halftoning that utilizes a partitioned look-up table and a parallel processing algorithm for concurrent look up of inverse halftone values for more than one pixel from the smaller look-up tables.
2. Description of the Related Art
In general, performance of an image forming apparatus, such as a printer, a multifunction copier or the like, is determined by factors such as print speed and image quality. Factors affecting the print speed include print resolution, print data transmission time from a host apparatus, such as a computer system, to the image forming apparatus, print data processing time in either the host apparatus and/or the image forming apparatus, and printing time of a printer engine in the image forming apparatus. Historically, printing speed has been largely determined by various mechanical limitations of the printer engine. In recent years, however, with improvements to increase the speed of the printer engine, the print data transmission time and the print data processing time have become the dominant factors in calculating overall print time.
The print data transmission time and the print data processing time are determined by a data exchange system between the host apparatus and the image forming apparatus. For example, if a printer driver executing in the host apparatus employs a graphics device interface (GDI) system that performs color matching, image rendering, etc., print data may be compressed by a compression algorithm in the host apparatus, such as the Joint Bi-level Image Expert Group (JBIG) algorithm, in order to reduce transmission time for the data to pass from the host apparatus to the image forming apparatus. The transmitted print data are then decompressed and printed in the image forming apparatus. On the other hand, if the printer driver employs a page description language (PDL) system, the print data are transmitted as, for example, descriptors that are processed entirely in the image forming apparatus to render the image, unlike in the GDI system.
FIG. 2 is a flowchart illustrating an example of a conventional process of transmitting print data from a host apparatus to an image forming apparatus. Referring to FIG. 2, at operation 100, halftoning is performed in the host apparatus on, for example, an 8-bit grayscale image having a resolution of 200×200 pixels, and the grayscale image is converted into a one-bit binary image having resolution of 200×200 pixels.
Halftoning is a reprographic technique that simulates continuous tone imagery through the use of dots, varying either in size or in spacing. Whereas continuous tone imagery (such as film photography, for example) contains a theoretically infinite range of colors or greys, the halftone process reduces visual reproductions to a binary image that is printed with only one color of ink. This binary reproduction relies on a basic optical illusion; i.e., that these tiny halftone dots are blended into smooth tones by the human eye.
Just as color photography evolved with the addition of filters and film layers, color printing is made possible by repeating the halftone process for each subtractive color, most commonly using what is generally referred to as the “CMYK color model” (the “cyan, magenta, yellow and black” model). The semi-opaque property of ink allows halftone dots of different colors to create another optical effect; i.e., full-color imagery.
Digital halftoning typically uses a raster image or bitmap within which each monochrome picture element or pixel may be on or off, represented by ink or no ink. Consequently, to emulate the photographic halftone cell, the digital halftone cell must contain groups of monochrome pixels within the same-sized cell area. The fixed location and size of these monochrome pixels compromises the high frequency/low frequency dichotomy of the photographic halftone method. Clustered multi-pixel dots cannot “grow” incrementally, but in jumps of one whole pixel. In addition, the placement of that pixel is slightly off-center. To minimize this compromise, the digital halftone monochrome pixels must be quite small, numbering from 600 to 2,540, or more, pixels per inch. However, digital image processing has also enabled more sophisticated dithering algorithms to decide which pixels to turn black or white, some of which yield better results than digital halftoning.
Returning to FIG. 2, JBIG compression (JBIG is a lossless image compression standard from the Joint Bi-level Image Experts Group, standardized as ISO/IEC standard 11544 and as ITU-T recommendation T.82.) is performed on the resultant binary image at operation 102 and the compressed binary image is transmitted from the host apparatus to an image forming apparatus at operation 104. At operation 106, JBIG decompression is performed on the binary image transmitted to the image forming apparatus. In this case, a high-capacity page memory is required to store the 200×200 one-bit image. Additionally, a large quantity of data must be transmitted since the compressed binary image also has a large quantity of data. If a page memory has the capacity to store an image transmitted from the host apparatus to the image forming apparatus, i.e., there is a large quantity of transmission data, a long time is required to transmit the data to fill the page memory, prior to which no printing is performed.
FIGS. 3 and 4 are flowcharts illustrating other examples of conventional processes to print data from a host apparatus to an image forming apparatus. FIG. 3 illustrates a case where the amount of data of an input image (hereinafter also referred to as “information quantity”) is reduced. In this example, operations 108, 110, 112 and 114 are similar to the operations 100, 102, 104 and 106 in the example of FIG. 2. The example of FIG. 3 additionally includes operation 116, where the 200×200 one-bit binary image decompressed in operation 114 is converted into a 200×200 8-bit grayscale image. Consequently, operation 116 increases the information quantity.
FIG. 4 illustrates a case where the size of an input image is reduced. In the example of FIG. 4, operations 120, 122, 124 and 126 are similar to operations 108, 110, 112 and 114 in the example of FIG. 3. The example of FIG. 4 additionally includes operation 118 where the size of an input image is reduced from 200×200 pixels to 100×100 pixels. The process of FIG. 4 further includes operation 128 to increase the spatial resolution of the 100×100 one-bit binary image, decompressed in operation 126, to produce a 200×200 one-bit binary image. The operation 128 expands the size of the image using an interpolation method or the like.
Using the above-described processes to reduce the information quantity or the size of the image prior to the transmission of the print data may result in a shortened transmission time. Specifically, print data to fill a page memory reduced to ⅛ its size otherwise can be transmitted in the example of FIG. 3 and print data to fill a page memory reduced to ¼ its size otherwise can be transmitted in the example of FIG. 4. Subsequent to print data transmission, the data to render the image in a desired size and resolution can be obtained by increasing the information quantity or the number of pixels in the recovered image.
FIG. 5 is a flowchart illustrating a conventional resolution increasing method using a look-up table (LUT). As illustrated in FIG. 5, at operation 130, a binary image is input, and an image process at operation 132 is performed by accessing a look-up table (not illustrated) to retrieve image data corresponding to an input block of the input binary image. When the image process is performed on all input blocks constituting the binary image at operation 134, the resolution increasing method is terminated.
In such a conventional method, the image process is performed using one predetermined look-up table respective of characteristics of the input binary image. In the case where the look-up table contains mean values of pixels obtained from a representative training image, artifacts, such as blurring, may occur in a resultant image pattern after the image processing of a specific input image.
In a wide variety of applications, the computations are replaced by look-up tables, as in the above, resulting in significantly reduced computation times. One such application is LUT-based inverse halftoning, in which the inverse halftoning of images is performed directly by accessing a LUT. The LUT needs to be pre-computed from a training set of images. The LUT operation begins with a p-bit vector (also referred to as a “template”) being retrieved from the source and being transmitted to the LUT that has already stored output values corresponding to that template. In this way, all templates are, one by one, retrieved from the halftone image and go through the LUT operation to obtain their output values of the inverse halftoning.
Digital halftoning has recently gained in popularity and importance due to the availability and adoption of bi-level devices, such as fax machines and plasma displays. The input to a digital halftoning system is an image whose pixels have more than two levels, for example 256, and the result of the halftoning process is an image that has only two levels.
Inverse halftoning is an operation involving the conversion of an image from its halftone version to a grey level image; i.e., from a two level image to, for example, a 256-level image. Inverse halftone operations have broad applications in areas where processing is required on printed images. The images are first scanned, then inverse halftoned, and then operations such as zooming, rotation and transformation may be applied. Standard compression techniques cannot process halftones directly. Thus, inverse halftoning is required before compression of printed images can be performed.
An exemplary look-up table method for inverse halftoning is described in the article “Look-Up Table (LUT) Method for Inverse Halftoning” by Murat Mese and P. P. Vaidyanathan, published in IEEE Tran. Image Processing, Vol. 10, No. 10, October 2001, which is herein incorporated by reference in its entirety.
This method represents a relatively fast and computation-free method of inverse halftoning, providing high quality images. The LUT method for inverse halftoning generally includes the following procedural steps. Using a template (represented by t), which is a group of pixels consisting of the pixel to be inverse halftoned and the pixels in its neighborhood. The LUT method for inverse halftoning uses four types of templates, namely: “16pels”, “19pels”, and “Rect”. The 16pels have 16 pixels, 19pels have 19 pixels and Rect have 21 pixels. One pixel is equal to one bit because pixels have bi-level values in halftone images. Each template has a pixel 0 that indicates the position of the pixel to be inverse halftoned, and the other neighborhood pixels are numbered from 1 to 18 (when the template type is 19pels).
The templates are retrieved from the halftone image following a raster-scan style, i.e. from left to right in a row, and from top to bottom of the image. A template is retrieved from the halftone image and goes to the LUT. The LUT returns the contone value that corresponds to the retrieved template. The results from the LUT form the output image. One template is retrieved and completes its inverse halftone operation using the LUT before the next template is retrieved.
The contents of the LUT used in the above LUT method are generated by building a training set of images that includes continuous-tone images and their respective halftone versions. The templates are retrieved from the halftone images and their contone level values are retrieved from the corresponding continuous-tone image. When a template occurs more than once in the training set, then its contone value is the mean of all contone values that corresponds to that template in the training set.
The LUT method of inverse halftoning is completely computation free and requires only LUT access when the same halftone algorithm (e.g., Floyd and Steinberg Error Diffusion) is used in the input halftone images and in the halftone images of the training set for LUT generation.
The LUT method for inverse halftoning can also be applied to color halftones. The color inverse halftoning includes three color planes (R, G, B), and each plane has its independent LUT. The templates, however, can contain pixels from different color plans.
Thus, a system and method for inverse halftoning using a partitioning look-up table solving the aforementioned problems is desired.